{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Search Suggestions System"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #string #binary-search #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #字符串 #二分查找 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: suggestedProducts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #搜索推荐系统"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个产品数组&nbsp;<code>products</code>&nbsp;和一个字符串&nbsp;<code>searchWord</code>&nbsp;，<code>products</code>&nbsp; 数组中每个产品都是一个字符串。</p>\n",
    "\n",
    "<p>请你设计一个推荐系统，在依次输入单词&nbsp;<code>searchWord</code> 的每一个字母后，推荐&nbsp;<code>products</code> 数组中前缀与&nbsp;<code>searchWord</code> 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。</p>\n",
    "\n",
    "<p>请你以二维列表的形式，返回在输入&nbsp;<code>searchWord</code>&nbsp;每个字母后相应的推荐产品的列表。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>products = [&quot;mobile&quot;,&quot;mouse&quot;,&quot;moneypot&quot;,&quot;monitor&quot;,&quot;mousepad&quot;], searchWord = &quot;mouse&quot;\n",
    "<strong>输出：</strong>[\n",
    "[&quot;mobile&quot;,&quot;moneypot&quot;,&quot;monitor&quot;],\n",
    "[&quot;mobile&quot;,&quot;moneypot&quot;,&quot;monitor&quot;],\n",
    "[&quot;mouse&quot;,&quot;mousepad&quot;],\n",
    "[&quot;mouse&quot;,&quot;mousepad&quot;],\n",
    "[&quot;mouse&quot;,&quot;mousepad&quot;]\n",
    "]\n",
    "<strong>解释：</strong>按字典序排序后的产品列表是 [&quot;mobile&quot;,&quot;moneypot&quot;,&quot;monitor&quot;,&quot;mouse&quot;,&quot;mousepad&quot;]\n",
    "输入 m 和 mo，由于所有产品的前缀都相同，所以系统返回字典序最小的三个产品 [&quot;mobile&quot;,&quot;moneypot&quot;,&quot;monitor&quot;]\n",
    "输入 mou， mous 和 mouse 后系统都返回 [&quot;mouse&quot;,&quot;mousepad&quot;]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>products = [&quot;havana&quot;], searchWord = &quot;havana&quot;\n",
    "<strong>输出：</strong>[[&quot;havana&quot;],[&quot;havana&quot;],[&quot;havana&quot;],[&quot;havana&quot;],[&quot;havana&quot;],[&quot;havana&quot;]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>products = [&quot;bags&quot;,&quot;baggage&quot;,&quot;banner&quot;,&quot;box&quot;,&quot;cloths&quot;], searchWord = &quot;bags&quot;\n",
    "<strong>输出：</strong>[[&quot;baggage&quot;,&quot;bags&quot;,&quot;banner&quot;],[&quot;baggage&quot;,&quot;bags&quot;,&quot;banner&quot;],[&quot;baggage&quot;,&quot;bags&quot;],[&quot;bags&quot;]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>products = [&quot;havana&quot;], searchWord = &quot;tatiana&quot;\n",
    "<strong>输出：</strong>[[],[],[],[],[],[],[]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= products.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= &Sigma; products[i].length &lt;= 2 * 10^4</code></li>\n",
    "\t<li><code>products[i]</code>&nbsp;中所有的字符都是小写英文字母。</li>\n",
    "\t<li><code>1 &lt;= searchWord.length &lt;= 1000</code></li>\n",
    "\t<li><code>searchWord</code>&nbsp;中所有字符都是小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [search-suggestions-system](https://leetcode.cn/problems/search-suggestions-system/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [search-suggestions-system](https://leetcode.cn/problems/search-suggestions-system/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"mobile\",\"mouse\",\"moneypot\",\"monitor\",\"mousepad\"]\\n\"mouse\"', '[\"havana\"]\\n\"havana\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.end = False\n",
    "        self.children = dict()\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.trie = TrieNode()\n",
    "    \n",
    "    def insert(self, product):\n",
    "        my_trie = self.trie\n",
    "        for ch in product:\n",
    "            if ch not in my_trie.children.keys():    \n",
    "                my_trie.children[ch] = TrieNode()\n",
    "            my_trie = my_trie.children[ch]\n",
    "        my_trie.end = True\n",
    "    \n",
    "    def search(self, prefix):\n",
    "        my_trie = self.trie\n",
    "        for ch in prefix:\n",
    "            if ch not in my_trie.children.keys():\n",
    "                return None\n",
    "            else:\n",
    "                my_trie = my_trie.children[ch]\n",
    "        return my_trie\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        products.sort()\n",
    "\n",
    "        trie = Trie()\n",
    "        for product in products:\n",
    "            trie.insert(product)\n",
    "        \n",
    "        def backtrack(trie_node, path, c_ans, prefix):\n",
    "            if len(c_ans) == 3:\n",
    "                    return\n",
    "            if trie_node.end:\n",
    "                c_ans.append(prefix+\"\".join(path.copy()))\n",
    "                \n",
    "            if len(trie_node.children)==0:\n",
    "                return\n",
    "            for elem in trie_node.children.keys():\n",
    "                path.append(elem)\n",
    "                backtrack(trie_node.children[elem], path, c_ans, prefix)\n",
    "                path.pop()\n",
    "        \n",
    "        ans = list()\n",
    "        \n",
    "        for i in range(len(searchWord)):\n",
    "            trie_node = trie.search(searchWord[:i+1])\n",
    "            if trie_node is None:\n",
    "                ans.append([])\n",
    "            else:\n",
    "                curr_ans = list()\n",
    "                backtrack(trie_node, list(), curr_ans, searchWord[:i+1])\n",
    "                ans.append(curr_ans.copy())\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        ans = []\n",
    "        products.sort()\n",
    "        n = len(searchWord)\n",
    "        for i in range(n):\n",
    "            tmp_ans = []\n",
    "            tmp_s = searchWord[:i+1]\n",
    "            print(tmp_s)\n",
    "            for i in products:\n",
    "                if len(tmp_ans) == 3:\n",
    "                    ans.append(tmp_ans)\n",
    "                    break\n",
    "                if i.startswith(tmp_s):\n",
    "                    tmp_ans.append(i)\n",
    "            else:\n",
    "                ans.append(tmp_ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        res,tmp = [], []\n",
    "        for i in range(1, len(searchWord) + 1):\n",
    "            for j in range(len(products)):\n",
    "                if searchWord[:i] == products[j][:i] :\n",
    "                    tmp.append(products[j])\n",
    "            tmp = sorted(tmp)\n",
    "            # print(tmp)\n",
    "            if len(tmp) > 3:\n",
    "                res.append(tmp[:3])\n",
    "            else:\n",
    "                res.append(tmp)\n",
    "            tmp = []\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        ans = []\n",
    "        products.sort()\n",
    "        checklist = products[:]\n",
    "        for i in range(len(searchWord)):\n",
    "            tmp = []\n",
    "            pattern = searchWord[:i+1]\n",
    "            for s in checklist:\n",
    "                if s.startswith(pattern):\n",
    "                    tmp.append(s)\n",
    "            tmp.sort()\n",
    "            checklist = tmp[:];\n",
    "            ans.append(tmp[:3])\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        products.sort()\n",
    "        n = len(products)\n",
    "        m = len(searchWord)\n",
    "        ans = []\n",
    "        i = 0\n",
    "        for s in accumulate(searchWord):\n",
    "            i = bisect_left(products, s, i)\n",
    "            a = []\n",
    "            for j in range(i, min(i + 3, n)):\n",
    "                if not products[j].startswith(s):\n",
    "                    break\n",
    "                a.append(products[j])\n",
    "            if not a:\n",
    "                ans += [a] * (m - len(ans))\n",
    "                return ans\n",
    "            ans.append(a)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        products=sorted(products)\n",
    "        total=[]\n",
    "        n=len(searchWord)\n",
    "        target=list(range(len(products)))\n",
    "        fake=list(range(len(products)))\n",
    "        for i in range(1,n+1):\n",
    "            solve=[]\n",
    "            temp=searchWord[:i]\n",
    "            for j in target:\n",
    "                if products[j][:i]==temp:\n",
    "                    solve.append(products[j])\n",
    "                    if len(solve)>=3:\n",
    "                        break\n",
    "                else:\n",
    "                    fake.remove(j)\n",
    "            target=fake.copy()\n",
    "            total.append(solve)\n",
    "\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        if not products and searchWord:\n",
    "            return []\n",
    "        result = []\n",
    "        cur_search_word = \"\"\n",
    "        for s in searchWord:\n",
    "            cur_res = []\n",
    "            cur_search_word += s\n",
    "            for word in products:\n",
    "                if word.startswith(cur_search_word):\n",
    "                    cur_res.append(word)\n",
    "            cur_res.sort()\n",
    "            result.append(cur_res[:3])\n",
    "            products = cur_res\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        dic=defaultdict(list)\n",
    "        n=len(searchWord)\n",
    "        \n",
    "        for word in products:\n",
    "            for i in range(1,min(n,len(word))+1):\n",
    "                if searchWord[:i]==word[:i]:\n",
    "                    dic[searchWord[:i]].append(word)\n",
    "        ans=[None]*n\n",
    "        for key in dic:\n",
    "            v=dic[key]\n",
    "\n",
    "            tmp=sorted(v)[:3]\n",
    "            ans[len(key)-1]=tmp\n",
    "   \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        lookup_table = collections.defaultdict(list)\n",
    "        products = sorted(products)\n",
    "        for p in products:\n",
    "            for i in range(1, len(p)+1):\n",
    "                if p[:i] not in lookup_table:\n",
    "                    lookup_table[p[:i]] = []\n",
    "                if len(lookup_table[p[:i]]) < 3:\n",
    "                    lookup_table[p[:i]].append(p)\n",
    "        ans = []\n",
    "        for i in range(1, len(searchWord)+1):\n",
    "            ans.append(lookup_table[searchWord[:i]])\n",
    "        \n",
    "        return ans\n",
    "                    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        output = []\n",
    "        for i in range(len(searchWord)):\n",
    "            sub = searchWord[0:i+1]\n",
    "            candidates = sorted([x for x in products if x[0:i+1] == sub])\n",
    "            if len(candidates) > 3:\n",
    "                candidates = candidates[:3]\n",
    "            output.append(candidates)\n",
    "\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        products.sort()\n",
    "        res = list()\n",
    "        quary = \"\"\n",
    "        for ch in searchWord:\n",
    "            quary += ch\n",
    "            start_ele = bisect.bisect_left(products, quary, 0)\n",
    "            res.append([s for s in products[start_ele : start_ele + 3] if s.startswith(quary)])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        products.sort()\n",
    "        query = \"\"\n",
    "        iter_last = 0\n",
    "        ans = list()\n",
    "        for ch in searchWord:\n",
    "            query += ch\n",
    "            iter_find = bisect.bisect_left(products, query, iter_last)\n",
    "            ans.append([s for s in products[iter_find : iter_find + 3] if s.startswith(query)])\n",
    "            iter_last = iter_find\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        products.sort()\n",
    "        ans = []\n",
    "        pre = ''\n",
    "        # print(products)\n",
    "        for x in searchWord:\n",
    "            pre += x\n",
    "            i = bisect_left(products, pre)\n",
    "            lis = []\n",
    "            for p in products[i:]:\n",
    "                if p[:len(pre)] == pre:\n",
    "                    lis.append(p)\n",
    "                    if len(lis) == 3: \n",
    "                        break\n",
    "                else:\n",
    "                    break\n",
    "            ans.append(lis)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        n = len(products)\n",
    "        products.sort()\n",
    "        ans = []\n",
    "        t = ''\n",
    "        for ch in searchWord:\n",
    "            t += ch\n",
    "            idx = bisect_left(products, t)\n",
    "            ans.append([products[i] for i in range(idx, min(idx + 3, n)) if products[i].startswith(t)])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        result = []\n",
    "        for i in range(len(searchWord)):\n",
    "            t = []\n",
    "            for pro in products:\n",
    "                if searchWord[:i+1] == pro[:i+1]:\n",
    "                    t.append(pro)\n",
    "            t.sort()\n",
    "            if len(t) > 2:\n",
    "                \n",
    "                result.append(t[0:3])\n",
    "            else:\n",
    "                result.append(t)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "\n",
    "        products.sort()\n",
    "        # print(products)\n",
    "        n = len(products)\n",
    "        res = []\n",
    "        lastidx = 0\n",
    "        sb = \"\"\n",
    "        for idx, c in enumerate(searchWord):\n",
    "            sb += c\n",
    "            k = 0\n",
    "            ans = []\n",
    "            \n",
    "            # for j in range(n):\n",
    "            #     if products[j].startswith(tmp):\n",
    "            #         k += 1\n",
    "            #         ans.append(products[j])\n",
    "            #     if k== 3:\n",
    "            #         break\n",
    "            # res.append(ans)\n",
    "            # 二分优化 - > 这是因为 顺序pro中，一定是大于当前关键词后三个\n",
    "            nowidx = bisect.bisect_left(products, sb, lastidx)\n",
    "            res.append([s for s in products[nowidx:nowidx+3] if s.startswith(sb)])\n",
    "\n",
    "            lastidx = nowidx\n",
    "            \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        # ans = SortedList()\n",
    "        # for pro in products:\n",
    "        #     if pro.startswith(\"mo\"):\n",
    "        #         ans.add(pro)\n",
    "        # print(ans[0:3])\n",
    "        ans = []\n",
    "        for i in range(len(searchWord)):\n",
    "            match = SortedList()\n",
    "            prefix = searchWord[0:i+1]\n",
    "            # print(prefix)\n",
    "            for product in products:\n",
    "                if product.startswith(prefix):\n",
    "                    match.add(product)\n",
    "            ans.append(list(match[0:3]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        products.sort()\n",
    "        wordsSet = set()\n",
    "        for i in range(len(searchWord)):\n",
    "            wordsSet.add(searchWord[0:i+1])\n",
    "        mapping = {}\n",
    "        for product in products:\n",
    "            for i in range(len(product)):\n",
    "                if(product[0:i+1] not in wordsSet):\n",
    "                    continue\n",
    "                if(product[0:i+1] not in mapping):\n",
    "                    mapping[product[0:i+1]] = []\n",
    "                if(len(mapping[product[0:i+1]]) < 3):\n",
    "                    mapping[product[0:i+1]].append(product)\n",
    "        result = [[] for i in range(len(searchWord))]\n",
    "        for i in range(len(searchWord)):\n",
    "            if(searchWord[0:i+1] not in mapping):\n",
    "                continue\n",
    "            result[i] = mapping[searchWord[0:i+1]]\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        products.sort()\n",
    "        wordsSet = set()\n",
    "        for i in range(len(searchWord)):\n",
    "            wordsSet.add(searchWord[0:i+1])\n",
    "        mapping = {}\n",
    "        for product in products:\n",
    "            for i in range(len(product)):\n",
    "                if(product[0:i+1] not in wordsSet):\n",
    "                    continue\n",
    "                if(product[0:i+1] not in mapping):\n",
    "                    mapping[product[0:i+1]] = []\n",
    "                if(len(mapping[product[0:i+1]]) < 3):\n",
    "                    mapping[product[0:i+1]].append(product)\n",
    "        result = [[] for i in range(len(searchWord))]\n",
    "        for i in range(len(searchWord)):\n",
    "            if(searchWord[0:i+1] not in mapping):\n",
    "                continue\n",
    "            result[i] = mapping[searchWord[0:i+1]]\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        d = dict()\n",
    "        n = len(products)\n",
    "        for i in range(n):\n",
    "            m = len(products[i]) + 1\n",
    "            for k in range(1, m):\n",
    "                s = products[i][:k]\n",
    "                if s in d:\n",
    "                    heapq.heappush(d[s], products[i])\n",
    "                else:\n",
    "                    pq = [products[i]]\n",
    "                    heapq.heapify(pq)\n",
    "                    d[s] = pq\n",
    "        m = len(searchWord) + 1\n",
    "        ans = [[] for _ in range(1, m)]\n",
    "        for i in range(1, m):\n",
    "            s = searchWord[:i]\n",
    "            if s in d:\n",
    "                step = 0\n",
    "                while d[s] and step < 3:\n",
    "                    ans[i - 1].append(heapq.heappop(d[s]))\n",
    "                    step += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "\n",
    "        # 字符串按字典序排列\n",
    "        products.sort()\n",
    "        # 构建Trie树\n",
    "        # trie={}\n",
    "        dic = collections.defaultdict(list)        \n",
    "        for word in products:\n",
    "            # root=trie\n",
    "            for i, c in enumerate(word):                \n",
    "                dic[word[:i+1]].append(word)\n",
    "                # if c not in root:\n",
    "                #     root[c]={}\n",
    "                # root=root[c]\n",
    "        # print(products, trie, dic)\n",
    "\n",
    "        res=[]\n",
    "        # 搜索\n",
    "        for i,c in enumerate(searchWord):\n",
    "            res.append(dic[searchWord[:i+1]][:3])\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, ps: List[str], w: str) -> List[List[str]]:\n",
    "        tr = defaultdict(lambda: defaultdict(int))\n",
    "        idx = 0\n",
    "        minMap, maxMap = {}, {}\n",
    "        def add(s, num):\n",
    "            nonlocal idx\n",
    "            p = 0\n",
    "            for c in s:\n",
    "                u = ord(c) - ord('a')\n",
    "                if tr[p][u] == 0:\n",
    "                    idx += 1\n",
    "                    tr[p][u] = idx\n",
    "                    minMap[tr[p][u]] = num\n",
    "                maxMap[tr[p][u]] = num\n",
    "                p = tr[p][u]\n",
    "        def query(s):\n",
    "            a, b, p = -1, -1, 0\n",
    "            for c in s:\n",
    "                u = ord(c) - ord('a')\n",
    "                if tr[p][u] == 0:\n",
    "                    return (-1, -1)\n",
    "                a = minMap[tr[p][u]]\n",
    "                b = maxMap[tr[p][u]]\n",
    "                p = tr[p][u]\n",
    "            return (a, b)\n",
    "        ps.sort()\n",
    "        ans = []\n",
    "        for i in range(len(ps)):\n",
    "            add(ps[i], i)\n",
    "        for i in range(len(w)):\n",
    "            l, r = query(w[:i + 1])\n",
    "            lst = [ps[j] for j in range(l, min(l + 3, r + 1)) if l != -1]\n",
    "            ans.append(lst)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        root = {'index': []}\n",
    "        ans = []\n",
    "        def insert(product, index):\n",
    "            node = root\n",
    "            for c in product:\n",
    "                if c not in node:\n",
    "                    node[c] = {}\n",
    "                    node[c]['index'] = []\n",
    "                node['index'].append(index)                    \n",
    "                node = node[c]\n",
    "            node['index'].append(index)\n",
    "        def search(prefix):\n",
    "            node = root\n",
    "            lists = []\n",
    "            for c in prefix:\n",
    "                if c not in node:\n",
    "                    return lists\n",
    "                node = node[c]\n",
    "            for index in node['index']:\n",
    "                lists.append(products[index])\n",
    "            lists.sort()\n",
    "            if len(lists) >= 3:\n",
    "                return lists[:3]\n",
    "            return lists\n",
    "        \n",
    "        i = 0\n",
    "        for product in products:\n",
    "            insert(product, i)\n",
    "            i += 1\n",
    "        for i in range(len(searchWord)):\n",
    "            ans.append(search(searchWord[:i+1]))\n",
    "        return ans\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        productTree = collections.defaultdict(list)\n",
    "        products = sorted(products)\n",
    "        \n",
    "        for product in products:\n",
    "            for i in range(len(product)):\n",
    "                if len(productTree[product[:i+1]]) < 3:\n",
    "                    productTree[product[:i+1]].append(product)\n",
    "        \n",
    "        return [productTree[searchWord[:k+1]] for k in range(len(searchWord))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        ab_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',\n",
    "           'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']\n",
    "\n",
    "        ab_dict = {}\n",
    "        for word in products:\n",
    "            tmp_dict = ab_dict\n",
    "            for let in word:\n",
    "                if let in tmp_dict:\n",
    "                    tmp_dict = tmp_dict[let]\n",
    "                else:\n",
    "                    tmp_dict[let] = {}\n",
    "                    tmp_dict = tmp_dict[let]\n",
    "            tmp_dict[0] = word\n",
    "\n",
    "        def find_word(tmp_dict, out_list):\n",
    "            if 0 in tmp_dict:\n",
    "                out_list.append(tmp_dict[0])\n",
    "                if len(out_list) == 3:\n",
    "                    return out_list\n",
    "            for i in ab_list:\n",
    "                if i in tmp_dict:\n",
    "                    out_list = find_word(tmp_dict[i], out_list)\n",
    "                    if len(out_list) == 3:\n",
    "                        return out_list\n",
    "            return out_list\n",
    "\n",
    "        def check_word(word, ab_dict):\n",
    "            tmp_dict = ab_dict\n",
    "            out = []\n",
    "            for let in word:\n",
    "                if let in tmp_dict:\n",
    "                    tmp_dict = tmp_dict[let]\n",
    "                else:\n",
    "                    return []\n",
    "            if not tmp_dict:\n",
    "                return []\n",
    "            else:\n",
    "                out = find_word(tmp_dict, out)\n",
    "            return out\n",
    "\n",
    "        out = []\n",
    "        for i in range(len(searchWord)):\n",
    "            out.append(check_word(searchWord[:i+1], ab_dict))\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.clds = [None]*26\n",
    "        self.is_end = False\n",
    "        self.word = ''\n",
    "\n",
    "    def insert(self, word: str) -> None:\n",
    "        p = self\n",
    "        for w in word:\n",
    "            k = ord(w)-ord('a')\n",
    "            if p.clds[k] == None:\n",
    "                p.clds[k] = Trie()\n",
    "            p = p.clds[k]\n",
    "        p.is_end = True\n",
    "        p.word = word\n",
    "\n",
    "    def search(self, word: str) -> bool:\n",
    "        p = self\n",
    "        for w in word:\n",
    "            k = ord(w)-ord('a')\n",
    "            if p.clds[k] == None:\n",
    "                return False\n",
    "            p = p.clds[k]\n",
    "        return p.is_end\n",
    "\n",
    "    def samePrefix(self, word: str):\n",
    "        p = self\n",
    "        for w in word:\n",
    "            k = ord(w)-ord('a')\n",
    "            if p.clds[k] == None:\n",
    "                return None\n",
    "            p = p.clds[k]\n",
    "        return p\n",
    "\n",
    "    def startsWith(self, prefix: str) -> bool:\n",
    "        p = self\n",
    "        for w in prefix:\n",
    "            k = ord(w)-ord('a')\n",
    "            if p.clds[k] == None:\n",
    "                return False\n",
    "            p = p.clds[k]\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        ans = []\n",
    "        # 建树\n",
    "        root = Trie()\n",
    "        for p in products:\n",
    "            root.insert(p)\n",
    "        p = root\n",
    "        for i, ch in enumerate(searchWord):\n",
    "            p = p.samePrefix(ch)\n",
    "            # bfs 遍历去获取p 下所有单词\n",
    "            if p == None:\n",
    "                # 添加\n",
    "                ans += [[] for _ in range(len(searchWord)-i)]\n",
    "                break\n",
    "            q = [p]\n",
    "            ans_phase = []\n",
    "            while len(q) > 0:\n",
    "                t = []\n",
    "                for node in q:\n",
    "                    if node.is_end:\n",
    "                        ans_phase.append(node.word)\n",
    "                    for cld in node.clds:\n",
    "                        if cld != None:\n",
    "                            t.append(cld)\n",
    "                q = t\n",
    "            ans_phase.sort()\n",
    "            ans.append(ans_phase[:3])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.child = {}\n",
    "        self.words = []\n",
    "        \n",
    "    def add(self, w):\n",
    "        if w not in self.words:\n",
    "            if len(self.words) >= 3:\n",
    "                if w < self.words[-1]:\n",
    "                    self.words = sorted(self.words[:2]+[w])\n",
    "            else:\n",
    "                self.words = sorted(self.words + [w])\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        root = Node()\n",
    "        for p in products:\n",
    "            cur = root\n",
    "            for c in p:\n",
    "                if c not in cur.child:\n",
    "                    cur.child[c] = Node()\n",
    "                cur = cur.child[c]\n",
    "                cur.add(p)\n",
    "        \n",
    "        res = []\n",
    "        cur = root\n",
    "        for q in searchWord:\n",
    "            if cur:\n",
    "                cur = cur.child.get(q,None)\n",
    "            if cur:\n",
    "                res.append(sorted(cur.words))\n",
    "            else:\n",
    "                res.append([])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.child = dict()\n",
    "        self.words = list()\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        def addWord(root, word):\n",
    "            cur = root\n",
    "            for ch in word:\n",
    "                if ch not in cur.child:\n",
    "                    cur.child[ch] = Trie()\n",
    "                cur = cur.child[ch]\n",
    "                cur.words.append(word)\n",
    "                cur.words.sort()\n",
    "                if len(cur.words) > 3:\n",
    "                    cur.words.pop()\n",
    "        root = Trie()\n",
    "        for word in products:\n",
    "            addWord(root, word)\n",
    "        \n",
    "        ans = list()\n",
    "        flag = False\n",
    "        cur = root\n",
    "        for ch in searchWord:\n",
    "            if flag or ch not in cur.child:\n",
    "                flag = True\n",
    "                ans.append(list())\n",
    "            else:\n",
    "                cur = cur.child[ch]\n",
    "                ans.append(cur.words)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.children = defaultdict(Node)\n",
    "        self.words = []\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    def add(self,word):\n",
    "        p = self.root\n",
    "        for ch in word:\n",
    "            p = p.children[ch]\n",
    "            p.words.append(word)\n",
    "            p.words.sort()\n",
    "            if len(p.words)>3:\n",
    "                p.words.pop()\n",
    "    \n",
    "    def search(self,searchWord):\n",
    "        ans = []\n",
    "        p = self.root\n",
    "        flag = False\n",
    "        for ch in searchWord:\n",
    "            if not p.children.get(ch) or flag:\n",
    "                ans.append([])\n",
    "                flag = True\n",
    "            else: \n",
    "                p = p.children[ch]\n",
    "                ans.append(p.words)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        trie = Trie()\n",
    "        for product in products:\n",
    "            trie.add(product)\n",
    "\n",
    "        return trie.search(searchWord)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "\n",
    "        def build(word, pool, res_word):\n",
    "            if len(res_word)>=3:\n",
    "                return\n",
    "            if 'end' in pool:\n",
    "                res_word.append(word)\n",
    "            # if 'list' in pool:\n",
    "            cnt = 0\n",
    "            for ww in sorted(pool.keys()):\n",
    "                if cnt >= 3:\n",
    "                    break\n",
    "                elif ww != 'end':\n",
    "                    cnt += 1\n",
    "                    build(word+ww, pool[ww], res_word)\n",
    "            return\n",
    "\n",
    "        pool = {}\n",
    "\n",
    "        for prod in products:\n",
    "            pool_ = pool\n",
    "            for ee in prod:\n",
    "                if ee not in pool_:\n",
    "                    pool_[ee] = {}\n",
    "                # if 'list' not in pool_:\n",
    "                #     pool_['list'] = set([ee])\n",
    "                # else:\n",
    "                #     pool_['list'].add(ee)\n",
    "                pool_ = pool_[ee]\n",
    "            pool_['end'] = True \n",
    "        \n",
    "        res = []\n",
    "        word = ''\n",
    "        pool_ = pool\n",
    "        for ix in range(len(searchWord)):\n",
    "            if res and res[-1] == []:\n",
    "                res.append([])\n",
    "                continue\n",
    "            word = word + searchWord[ix]\n",
    "            if searchWord[ix] in pool_:\n",
    "                res_ = []\n",
    "                pool_ = pool_[searchWord[ix]]\n",
    "                build(word, pool_, res_)\n",
    "                res.append(res_)\n",
    "            else:\n",
    "                res.append([])\n",
    "\n",
    "        return res\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products, searchWord: str):\n",
    "        root = {\"children\": {}}\n",
    "        node = root\n",
    "        for product in products:\n",
    "            for ch in product:\n",
    "                children = node['children']\n",
    "                if ch not in children:\n",
    "                    children[ch] = {'children': {}, \"products\": []}\n",
    "                children[ch]['products'].append(product)\n",
    "                node = children[ch]\n",
    "            node = root\n",
    "\n",
    "        ans = []\n",
    "        flag = True\n",
    "        node = root\n",
    "        for ch in searchWord:\n",
    "            if ch not in node['children'] or not flag:\n",
    "                flag = False\n",
    "                ans.append([])\n",
    "            else:\n",
    "                node = node['children'][ch]\n",
    "                node[\"products\"].sort()\n",
    "                ans.append(node['products'][:3])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        def find(root, word):\n",
    "            p = root\n",
    "            i = 0\n",
    "            n = len(word)\n",
    "            while i < n:\n",
    "                c = word[i]\n",
    "                if c not in p:\n",
    "                    break\n",
    "\n",
    "                p = p[c]\n",
    "                i += 1\n",
    "\n",
    "            return p, i\n",
    "\n",
    "        def insert(root, word):\n",
    "            p, i = find(root, word)\n",
    "            n = len(word)\n",
    "            while i < n:\n",
    "                c = word[i]\n",
    "                p[c] = {}\n",
    "                p = p[c]\n",
    "                i += 1\n",
    "\n",
    "            p[''] = ''\n",
    "\n",
    "        def dfs(root, prefix, curr, ans):\n",
    "            if len(ans) >= 3:\n",
    "                return\n",
    "\n",
    "            if not root:\n",
    "                ans.append(prefix + ''.join(curr))\n",
    "                return\n",
    "\n",
    "            for c in sorted(root.keys()):\n",
    "                curr.append(c)\n",
    "                dfs(root[c], prefix, curr, ans)\n",
    "                curr.pop()\n",
    "\n",
    "        root = {}\n",
    "        for w in products:\n",
    "            insert(root, w)\n",
    "\n",
    "        ans = []\n",
    "        n = len(searchWord)\n",
    "        for i in range(1, n + 1):\n",
    "            l = []\n",
    "            s = searchWord[:i]\n",
    "            f, j = find(root, s)\n",
    "            if j < i:\n",
    "                ans.append([])\n",
    "            else:\n",
    "                dfs(f, s, [], l)\n",
    "                ans.append(l)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.looksup = {}\n",
    "\n",
    "    def insert(self, word):\n",
    "        tree = self.looksup\n",
    "        for s in word:\n",
    "            if s not in tree.keys():\n",
    "                tree[s] = {}\n",
    "            tree = tree[s]\n",
    "        tree['#'] = '#'\n",
    "\n",
    "    def search_prefix(self, prefix):\n",
    "        tree = self.looksup\n",
    "        for s in prefix:\n",
    "            if s not in tree.keys():\n",
    "                return []\n",
    "            tree = tree[s]\n",
    "        # print(f\"tree: {tree.keys()}\")\n",
    "        res = []\n",
    "        def dfs(tree, prefix):\n",
    "            for x in sorted(tree.keys())[:3]:\n",
    "                if tree[x] == \"#\":\n",
    "                    res.append(prefix)\n",
    "                else: \n",
    "                    dfs(tree[x], prefix + x)\n",
    "        dfs(tree, prefix)\n",
    "        return res[:3]\n",
    "                \n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        trie = Trie()\n",
    "        for product in products:\n",
    "            trie.insert(product)\n",
    "        recommeded = []\n",
    "        for sub_len in range(len(searchWord)):\n",
    "            sub_rec = trie.search_prefix(searchWord[:sub_len+1])\n",
    "            recommeded.append(sub_rec)\n",
    "        return recommeded\n",
    "                                                                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class trie:\n",
    "    def __init__(self):\n",
    "        self.isend = False\n",
    "        self.next = [False] * 26\n",
    "\n",
    "    def insert(self, s):\n",
    "        node = self\n",
    "        for i in s:\n",
    "            idx = ord(i) - ord('a')\n",
    "            if not node.next[idx]:\n",
    "                new_node = trie()\n",
    "                node.next[idx] = new_node\n",
    "            node = node.next[idx]\n",
    "        node.isend = True\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        my_trie = trie()\n",
    "        for i in products:\n",
    "            my_trie.insert(i)\n",
    "        \n",
    "        def find(node, s):\n",
    "            out = []\n",
    "            for i in s:\n",
    "                idx = ord(i) - ord('a')\n",
    "                if node.next[idx]:\n",
    "                    node = node.next[idx]\n",
    "                else:\n",
    "                    return out\n",
    "        \n",
    "            def huisu(node, s):\n",
    "                if len(out) == 3:\n",
    "                    return \n",
    "                if node.isend:\n",
    "                    out.append(s)\n",
    "                \n",
    "                for i in range(26):\n",
    "                    if node.next[i]:\n",
    "                        huisu(node.next[i], s+chr(ord('a')+i))\n",
    "            \n",
    "            huisu(node, s)\n",
    "            return out\n",
    "        result = []\n",
    "        for i in range(len(searchWord)):\n",
    "            result.append(find(my_trie, searchWord[0:i+1]))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.children = [None] * 26\n",
    "        self.is_leaf = False\n",
    "    \n",
    "    def insert(self, word):\n",
    "        cur = self\n",
    "        for c in word:\n",
    "            idx = ord(c) - ord('a')\n",
    "            if not cur.children[idx]:\n",
    "                cur.children[idx] = Trie()\n",
    "            cur = cur.children[idx]\n",
    "        cur.is_leaf = True\n",
    "\n",
    "    def search(self, word):\n",
    "        cur = self\n",
    "        for c in word:\n",
    "            idx = ord(c) - ord('a')\n",
    "            if not cur.children[idx]:\n",
    "                return\n",
    "            cur = cur.children[idx]\n",
    "        return cur\n",
    "\n",
    "class Solution:\n",
    "    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:\n",
    "        trie = Trie()\n",
    "        for prod in products:\n",
    "            trie.insert(prod)\n",
    "        lst = []\n",
    "        for l in range(1, len(searchWord) + 1):\n",
    "            res = trie.search(searchWord[:l])\n",
    "            cur_lst = []\n",
    "            self.dfs(res, searchWord[:l], cur_lst)\n",
    "            lst.append(cur_lst)\n",
    "        return lst\n",
    "    \n",
    "    def dfs(self, cur, path, lst):\n",
    "        if len(lst) >= 3:\n",
    "            return\n",
    "        if not cur:\n",
    "            return\n",
    "        if cur.is_leaf:\n",
    "            lst.append(path)\n",
    "        for i in range(26):\n",
    "            if not cur.children[i]:\n",
    "                continue\n",
    "            path += chr(i + ord('a'))\n",
    "            self.dfs(cur.children[i], path, lst)\n",
    "            path = path[:-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
